1. Field of the Invention
The present invention relates to a wireless tag, a reader/writer, an encoding system for an ID transmitted by the wireless tag, and an encoding method, and particularly relates to a wireless tag, a reader/writer, an encoding system, and an encoding method, which give confidential variability to an ID transmitted by the wireless tag while enabling a circuit of the wireless tag to be downsized and reducing the load of a decoding process.
2. Description of the Related Art
Recently, IC cards including wireless tags and devices such as mobile terminal devices are widely used. A wireless tag is a small device that includes an antenna for wireless communication and an IC that stores a unique ID, and is also known as a radio frequency identification (RFID). The unique ID stored in the wireless tag is read by a device known as a reader/writer via a wireless communication, and used in various types of processes.
While wireless tags have a wide range of applications and are remarkably useful, they are problematic with regard to privacy protection. IDs are currently exchanged as fixed values between the wireless tag and the reader/writer. Consequently, when identical wireless tags are used in a plurality of locations, a person who somehow manages to obtain a usage history of the wireless ID can track the movements of its owners.
Non-Patent Literatures 1 and 2 disclose examples of techniques that attempt to solve this problem by encoding the ID to a different value each time it is exchanged between the wireless tag and the reader/writer, thereby giving the ID confidential variability.
Hash chain methods disclosed in the Non-Patent Literatures 1 and 2 give confidential variability to an ID by using a random one-way hash function to re-encrypt it.    [Non-Patent Literature 1]: Shingo KINOSHITA, “Consideration on RFID privacy”, [online], Sep. 16, 2004, Nikkei Business Publications, Inc., [Searched on Jul. 7, 2005], Internet<URL:http://itpro.nikkeibp.co.jp/free/NBY/RFID/20040913/1/>    [Non-Patent Literature 2]: M. Ohkubo, K. Suzuki, and S. Kinoshita, Cryptographic approach to “privacy-friendly” tags. In RFID Privacy Workshop, MIT, USA, 2003. [Searched on Jul. 7, 2005], Internet<URL:http://lasecwww.epfl.ch/˜gavoine/download/Avoine0-2005-persec.pdf>
However, hash chain methods are problematic in that the circuit becomes too large for current technological levels. Given current technological levels, the circuit size allocated for security function of a wireless tag is at best 200 to 2000 gates, yet more than several tens of thousands of gates are needed to realize a hash function of sufficient capability. A circuit of this size is too large for a wireless tag, where downsizing and low cost are demanded.
Hash chain methods also have a problem of load during the ID decoding process. A one-way hash function cannot make a back calculation from an encoded ID to an original ID. To determine the original ID, all candidates for the original ID must be stored and repeatedly encoded with a hash function until the ID that is the decoding target appears. When the number of wireless tags whose IDs need decoding increases, the load of the decoding process becomes enormous.